#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <vector>
using namespace std;

//int main() {
//    int n = 0;
//    cin >> n;
//    vector<int> v = { 0 , 1 };
//    while (n > v.back())
//    {
//        v.push_back(v[v.size() - 1] + v[v.size() - 2]);
//    }
//
//    int greater = v[v.size() - 1];
//    int smaller = v[v.size() - 2];
//
//
//    if (abs(smaller - n) > abs(greater - n))
//        cout << abs(greater - n);
//    else
//        cout << abs(smaller - n);
//}

//string solve(string s, string t) {
//    // write code here
//
//    string s3;
//
//    int next = 0;
//    int end1 = s.size() - 1;
//    int end2 = t.size() - 1;
//
//    while (end1 >= 0 || end2 >= 0)
//    {
//        int x1 = end1 < 0 ? 0 : s[end1--] - '0';
//        int x2 = end2 < 0 ? 0 : t[end2--] - '0';
//        int count = x1 + x2 + next;
//
//        next = count / 10;
//        count %= 10;
//
//        s3.push_back(count + '0');
//    }
//    if (next)
//    {
//        s3.push_back(1 + '0');
//    }
//    reverse(s3.begin(), s3.end());
//
//    cout << s3 << endl;
//    return s3;
//}

struct ListNode {
    int val;
    struct ListNode* next;
    ListNode(int x) 
        : val(x), 
        next(nullptr) 
    {}
};
ListNode* reverseList(ListNode* head)
    {
        ListNode* cur = head;
        ListNode* newhead = nullptr;
        while(cur)
        {
            ListNode* next = cur->next;
            cur->next = newhead;
            newhead = cur;
            cur = next;
        }

        return newhead;
    }
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        head1 = reverseList(head1);
        head2 = reverseList(head2);

        ListNode* phead = new ListNode(0);
        ListNode* cur = phead;
        int next = 0;

        while(head1 || head2)
        {
            int x1 = head1 == nullptr ? 0 : head1->val;
            int x2 = head2 == nullptr ? 0 : head2->val;
            int count = x1 + x2 + next;

            next = count / 10;
            count %= 10;

            cur->next = new ListNode(count);
            cur = cur->next;

            if(head1)
                head1 = head1->next;
            if(head2)
                head2 = head2->next;
        }

        ListNode* newhead = reverseList(phead->next);

        return newhead;
    }
int main()
{
    ListNode* n1 = new ListNode(9);
    n1->next = new ListNode(3);
    n1->next->next = new ListNode(7);

    ListNode* n2 = new ListNode(6);
    n2->next = new ListNode(3);

    addInList(n1, n2);
    return 0;
}